/**
 * https://leetcode-cn.com/problems/sort-colors/
 * 0, 1, 2排序
 * @param nums 
 */
const sortColors = (nums: number[]): void => {
    if (nums.length < 2) return;
    const len = nums.length;
    // 只有左边为0才移动
    let li = 0,
        // 移动的指针
        m = 0,
        // 只有右边为2时才移动
        ri = len - 1;


    while (m <= ri) {
        // 值为2
        if (nums[m] === 2) {
            // 和末尾元素交换位置
            // [nums[ri], nums[m]] = [nums[m], nums[ri]]
            nums[ri] = (nums[ri] + nums[m]) - (nums[m] = nums[ri])
            // ri往前移动 
            // m不移动，可能交换之后m位置还可能是2
            ri--;
            continue
        } else if (nums[m] === 0) {

            // 只有m和li不相等时, li和m交换位置
            if (li !== m) {
                nums[li] = (nums[li] + nums[m]) - (nums[m] = nums[li])
            }

            // li, m往后走
            li++
        }
        m++
    }

};
/**
 * https://leetcode-cn.com/problems/sort-colors/
 * 0, 1, 2排序
 * @param nums 
 */
const sortColors3 = (nums: number[]): void => {
    if (nums.length < 2) return;
    const len = nums.length;
    // 只有左边为0才移动
    let li = 0,
        // 移动的指针
        // 只有右边为2时才移动
        ri = len - 1;

    for (let i = 0; i < len && i <= ri; i++) {
        // 值为2
        if (nums[i] === 2) {
            // 和末尾元素交换位置
            const tmp = nums[ri];
            nums[ri] = nums[i];
            nums[i] = tmp
            // ri往前移动 
            // m不移动，可能交换之后m位置还可能是2
            ri--;

            // i保存不动
            i = i - 1;
        } else if (nums[i] === 0) {
            // 只有m和li不相等时, li和m交换位置
            if (li !== i) {
                const tmp = nums[li];
                nums[li] = nums[i];
                nums[i] = tmp
            }

            // li, m往后走
            li++
        }
    }

};

const sortColors2 = (nums: number[]): void => {
    if (nums.length < 2) return;
    const len = nums.length;
    // 只有左边为0才移动
    let li = 0,
        // 移动的指针
        m = 0,
        // 只有右边为2时才移动
        ri = len - 1;

    /**
     * 交换元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp
    }

    // 必须等于ri, 否则 [2, 0, 1]不通过
    while (m <= ri) {
        const e = nums[m]
        // 值为2
        if (e === 2) {
            // 和末尾元素交换位置
            swap(ri, m)
            // ri往前移动 
            // m不移动，可能交换之后m位置还可能是2
            ri--;
        } else if (e === 1) {
            // m向右移动
            m++
        } else {
            // e === 0

            // 只有m和li不相等时, li和m交换位置
            if (li !== m) {
                swap(li, m)
            }

            // li, m往后走
            li++
            m++
        }
    }
};



// const arr = [2, 0, 2, 1, 1, 0]
// const arr = [2,0,1]
// const arr = [1]
const arr = [2, 2]
sortColors(arr);
console.log(arr);